package _18_剑指OfferII;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class _107_剑指OfferII矩阵中的距离 {

    // 动态规划计算
    public int[][] updateMatrix(int[][] mat) {
        // 取4个方向的动态规划，求解问题
        int rows = mat.length;
        int cols = mat[0].length;
        int[][] result = new int[rows][cols];
        for (int i = 0; i < rows; ++i) {
            Arrays.fill(result[i], Integer.MAX_VALUE >> 1);
        }
        // 初始化dp数据
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (mat[i][j] == 0) {
                    result[i][j] = 0;
                }
            }
        }
        // 4个方向动态规划
        // 动态规划计算 左，上
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (i - 1 >= 0) {
                    result[i][j] = Math.min(result[i][j], result[i - 1][j] + 1);
                }
                if (j - 1 >= 0) {
                    result[i][j] = Math.min(result[i][j], result[i][j - 1] + 1);
                }
            }
        }

        // 动态规划计算 左，下
        for (int i = rows - 1; i >= 0; i--) {
            for (int j = 0; j < cols; j++) {
                if (i + 1 < rows) {
                    result[i][j] = Math.min(result[i][j], result[i + 1][j] + 1);
                }
                if (j - 1 >= 0) {
                    result[i][j] = Math.min(result[i][j], result[i][j - 1] + 1);
                }
            }
        }

        // 动态规划计算 右，上
        for (int i = 0; i < rows; i++) {
            for (int j = cols - 1; j >= 0; j--) {
                if (i - 1 >= 0) {
                    result[i][j] = Math.min(result[i][j], result[i - 1][j] + 1);
                }
                if (j + 1 < cols) {
                    result[i][j] = Math.min(result[i][j], result[i][j + 1] + 1);
                }
            }
        }

        // 动态规划计算 右，下
        for (int i = rows - 1; i >= 0; i--) {
            for (int j = cols - 1; j >= 0; j--) {
                if (i + 1 < rows) {
                    result[i][j] = Math.min(result[i][j], result[i + 1][j] + 1);
                }
                if (j + 1 < cols) {
                    result[i][j] = Math.min(result[i][j], result[i][j + 1] + 1);
                }
            }
        }
        return result;
    }


    // 广度优先搜索, 并且采用以0为起点搜索
    public int[][] updateMatrix1(int[][] mat) {
        int[][] m = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int row = mat.length;
        int col = mat[0].length;
        int[][] results = new int[row][col];
        boolean[][] visited = new boolean[row][col];
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (mat[i][j] == 0) queue.add(new int[]{i, j});
            }
        }

        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            for (int[] ints : m) {
                int newRow = poll[0] + ints[0];
                int newCol = poll[1] + ints[1];
                if (newRow >= row && newRow < row && newCol >= 0 && newCol < col && !visited[newRow][newCol] && mat[newRow][newCol] != 0) {
                    visited[newRow][newCol] = true;
                    results[newRow][newCol] = results[poll[0]][poll[1]] + 1;
                    queue.add(new int[]{newRow, newCol});
                }
            }
        }
        return results;
    }

}
